#include "ZeroPopulation.h"
#include "ZeroGene.h"

#include <iostream>
#include <cstdlib>
#include <cmath>

const int ZeroPopulation::C_DefaultCapacity = 4096;
const int ZeroPopulation::C_DefaultExpander = 1024;

ZeroPopulation::ZeroPopulation()
{
	mZPopSize = 0;
	mZPopCapacity = C_DefaultCapacity;
	mZEntities = new ZeroEntity*[mZPopCapacity];
	mNewPopSize = 0;
	mNewPopCapacity = C_DefaultCapacity;
	mNewEntities = new ZeroEntity*[mNewPopCapacity];
	mMutex = new ZeroMutex();
	mNewMutex = new ZeroMutex();
}

ZeroPopulation::~ZeroPopulation()
{
	if (mZEntities) {
		for (int i = 0;i < mZPopSize;i++)
			delete mZEntities[i];
		delete [] mZEntities;
	}
	if (mNewEntities) {
		for (int i = 0;i < mNewPopSize;i++)
			delete mNewEntities[i];
		delete [] mNewEntities;
	}
	if (mMutex)
		delete mMutex;
	if (mNewMutex)
		delete mNewMutex;
}

void ZeroPopulation::storeEntity(ZeroEntity *entity)
{
	mNewMutex->lock();
	if (mNewPopSize == mNewPopCapacity) {
		ZeroEntity **entities;
		mNewPopCapacity += C_DefaultExpander;
		entities = new ZeroEntity*[mNewPopCapacity];
		for (int i = 0;i < mNewPopSize;i++)
			entities[i] = mNewEntities[i];
		delete [] mNewEntities;
		mNewEntities = entities;
	}
	mNewEntities[mNewPopSize++] = entity;
	mNewMutex->unlock();
}

int ZeroPopulation::getSize()
{
	int size;
	mMutex->lock();
	size = mZPopSize;
	mMutex->unlock();
	return size;
}

ZeroEntity* ZeroPopulation::getEntity(int index)
{
	ZeroEntity *entity = NULL;
	mMutex->lock();
	if (index >= 0 && index < mZPopSize)
		entity = mZEntities[index];
	mMutex->unlock();
	return entity;
}

ZeroEntity* ZeroPopulation::randomSelect()
{
	ZeroEntity *entity = NULL;
	mMutex->lock();
	if (mZPopSize)
		entity = mZEntities[rand() % mZPopSize];
	mMutex->unlock();
	return entity;
}

ZeroEntity* ZeroPopulation::prioritySelect(int level)
{
	ZeroEntity *entity = NULL;
	int index = mZPopSize - 1;
	if (level < 0)
		return NULL;
	for (int i = 0;i <= level;i++)
		index = rand() % (index + 1);
	mMutex->lock();
	entity = mZEntities[index];
	mMutex->unlock();
	return entity;
}

void ZeroPopulation::dumpStatus()
{
	int N = 0, X = 0, X2 = 0, Xmax = 0, Xmin = 2147483647;
	ZeroGene *tmpGene;
	mMutex->lock();
	std::cout << "Population size: " << mZPopSize << std::endl;
	std::cout << "Population capacity: " << mZPopCapacity << std::endl;
	for (int i = 0;i < mZPopSize;i++) {
		for (int j = 0;j < mZEntities[i]->getGeneCount();j++) {
			tmpGene = mZEntities[i]->getGene(j);
			N += 2;
			X += tmpGene->getGeneFSize();
			X2 += tmpGene->getGeneFSize() * tmpGene->getGeneFSize();
			X += tmpGene->getGeneMSize();
			X2 += tmpGene->getGeneMSize() * tmpGene->getGeneMSize();
			if (tmpGene->getGeneFSize() < Xmin)
				Xmin = tmpGene->getGeneFSize();
			if (tmpGene->getGeneFSize() > Xmax)
				Xmax = tmpGene->getGeneFSize();
			if (tmpGene->getGeneMSize() < Xmin)
				Xmin = tmpGene->getGeneMSize();
			if (tmpGene->getGeneMSize() > Xmax)
				Xmax = tmpGene->getGeneMSize();
		}
	}
	std::cout << "GeneSize mean:" << (X / N) << ", max:" << Xmax << ", min:" << Xmin << std::endl;
	std::cout << "SD:" << sqrt(X2 / N - (X / N) * (X / N)) << std::endl;
/*
	std::cout << "============== Entities ===============" << std::endl;
	for (int i = 0;i < mZPopSize;i++)
		std::cout << mZEntities[i]->getScore() << " ";
	std::cout << std::endl << "============= New Entities ==============" << std::endl;
	for (int i = 0;i < mNewPopSize;i++)
		std::cout << mNewEntities[i]->getScore() << " ";
	std::cout << std::endl;
*/
	mMutex->unlock();
}

void ZeroPopulation::reSort()
{
	mMutex->lock();
	sort(mZEntities, mZPopSize);
	mMutex->unlock();
}

void ZeroPopulation::merge()
{
	mNewMutex->lock();
	sort(mNewEntities, mNewPopSize);
	mMutex->lock();
	if (mZPopSize + mNewPopSize > mZPopCapacity) {
		ZeroEntity **entities;
		mZPopCapacity = mZPopSize + mNewPopSize + C_DefaultExpander;
		entities = new ZeroEntity*[mZPopCapacity];
		int aIndex = mZPopSize - 1, bIndex = mNewPopSize - 1;
		mZPopSize += mNewPopSize;
		mNewPopSize = 0;
		for (int i = mZPopSize - 1;i >= 0;) {
			if (aIndex < 0)
				for (;i >= 0;)
					entities[i--] = mNewEntities[bIndex--];
			else if (bIndex < 0)
				for (;i >= 0;)
					entities[i--] = mZEntities[aIndex--];
			else if (mZEntities[aIndex]->getScore() > mNewEntities[bIndex]->getScore())
				entities[i--] = mNewEntities[bIndex--];
			else
				entities[i--] = mZEntities[aIndex--];
		}
		delete [] mZEntities;
		mZEntities = entities;
	} else {
		int aIndex = mZPopSize - 1, bIndex = mNewPopSize - 1;
		mZPopSize += mNewPopSize;
		mNewPopSize = 0;
		for (int i = mZPopSize - 1;i >= 0;) {
			if (bIndex < 0)
				break;
			else if (aIndex < 0)
				for (;i >= 0;)
					mZEntities[i--] = mNewEntities[bIndex--];
			else if (mZEntities[aIndex]->getScore() > mNewEntities[bIndex]->getScore())
				mZEntities[i--] = mNewEntities[bIndex--];
			else
				mZEntities[i--] = mZEntities[aIndex--];
		}
	}
	mMutex->unlock();
	mNewMutex->unlock();
}

void ZeroPopulation::sort(ZeroEntity **entities, int size)
{
	struct Segment {
		Segment() {}
		Segment(int ss, int ee) : s(ss), e(ee) {}
		Segment(Segment &seg) { s = seg.s; e = seg.e; }
		int s, e;
	} cur, st[size / 3 + 1];
	int top = 1, ssize, sp, spScore;
	st[0] = Segment(0, size - 1);
	while (top > 0) {
		cur = st[--top];
		ssize = cur.e - cur.s + 1;
		sp = cur.s + (rand() % ssize);
		spScore = entities[sp]->getScore();
		swap(entities[sp], entities[cur.e]);
		sp = cur.s;
		for (int i = cur.s;i < cur.e;i++)
			if (entities[i]->getScore() >= spScore)
				swap(entities[i], entities[sp++]);
		swap(entities[cur.e], entities[sp]);
		if (cur.s < sp - 1)
			st[top++] = Segment(cur.s, sp-1);
		if (sp + 1 < cur.e)
			st[top++] = Segment(sp + 1, cur.e);
	}
}

void ZeroPopulation::swap(ZeroEntity* &a, ZeroEntity* &b)
{
	ZeroEntity *t = a;
	a = b;
	b = t;
}
